﻿//1385. 两个数组间的距离值
//给你两个整数数组 arr1 ， arr2 和一个整数 d ，请你返回两个数组之间的 距离值 。
//「距离值」 定义为符合此距离要求的元素数目：对于元素 arr1[i] ，不存在任何元素 arr2[j] 满足 | arr1[i] - arr2[j]| <= d 。



//二分

class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d)
    {
        sort(arr2.begin(), arr2.end());
        int ans = 0;
        for (int x : arr1)
        {
            auto it = lower_bound(arr2.begin(), arr2.end(), x - d);
            if (it == arr2.end() || *it > x + d)
            {
                ans++;
            }
        }
        return ans++;
    }
};



//双指针

class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d)
    {
        ranges::sort(arr1);
        ranges::sort(arr2);
        int ans = 0;
        int j = 0;
        for (int x : arr1)
        {
            while (j < arr2.size() && arr2[j] < x - d)
            {
                j++;
            }
            if (j == arr2.size() || arr2[j] > x + d)
            {
                ans++;
            }
        }
        return ans;
    }
};